package mediumNumber;

/**
 * @desc:题目描述
 * 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
 * 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
 * 我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
 *
 * 保存数字的数字为 A ，长度为 n
 *
 * 我思路是:
 * 搞两个堆，一个堆方比较小的值，一个堆里面放比较大的值。
 *       /|        /|
 *     /  |      /  |
 *   /    |    /    |
 *  -------   -------
 *     A         B
 *  其中 A 是存放比较小的值，B 是存放比较大的值。
 *  我们每次取出新值 n 的时候，和 A 中的最大值 Amax 比较一下，如果 Amax <= n ，则放入 A 中，否则放入 B 中。
 *  假如，所有的数字个数是偶数个，则我们需要从最小堆里面取到最大的那个值（a），从较大的堆里面，取出最小的那个值（b），
 *       我们需要的结果就是 (a+b)/2
 *  假如，所有的数字个数是奇数个，则之间返回这个数字即可。
 *  那么，如何快速的从较小堆里面取出最大的那个值，又如何从较大堆哪里取出最小的值呢。
 *  这里还用用到大根堆和小根堆的知识。大根堆就是根节点上的值最大的堆，小根堆正好相反。所以，如果我们将较小的值放到大根堆里面，
 *
 * @author wangyifei
 */
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.stream.IntStream;

public class Solution3 {
    private boolean odl = true ;
    private int smallMax = -1 ;
    private int bigMin = Integer.MAX_VALUE ;
    private int counter = 0 ;

    public void insert(int i){
        counter++;
        if(odl){
            // odl 为 true , 说明者是 i  是第奇数个数字，此时 big 和 small 两个堆里面元素个数是相等的。
            // 此时要让小堆里面多一个
            // 如果 i 大于 small 里面的最大值，则需要将 big 里面的最小值放到 small 里面，然后将 i 放入到
            if( smallMax == -1 || smallMax >= i ){
                // do nothing
                smallMax = (smallMax == -1)?i:smallMax;
            }else{
                smallMax = (bigMin != -1)?bigMin:smallMax;
                bigMin = (bigMin > i )? i : bigMin ;
            }

        }else{
            // odl 为 false 的时候，i 为偶数，说明两个堆里面的数字数量不相等。small 要大一些。此时要让大堆里面多一个。
            // 如果 i 比 small 里面的最大值小，则要将 small 里面的最大值放到 big 里面，然后将 i 放到 samll 里面，这样
            // 两个堆就平衡了。
            if( bigMin <= i ){
                bigMin = (bigMin == -1)?i:bigMin;
            }else{
                bigMin = smallMax;
                smallMax = (smallMax < i)?i:smallMax;
            }
        }
        odl = !odl;
    }
    public double getMedium(){
        Double rs = 0D ;
        if( counter%2 == 1 ){
            rs = Double.valueOf(smallMax);
        }else {
            rs = Double.valueOf(smallMax+bigMin)/2;
        }
        return rs ;
    }
    public static void main(String[] args) {
        Solution3 s = new Solution3();
        ArrayList<Integer> ls = new ArrayList<>();
//        IntStream.range(0,12).forEach((i)->{
//            Integer i1 = Integer.parseInt(("" + Math.random()).substring(3,4));
//            ls.add(i1);
//        });
        //0 1 1 1 3 3 4 5 5 6 9 9
        ls.add(5);
        ls.add(3);
        ls.add(6);
        ls.add(5);
        ls.add(1);
        ls.add(1);
        ls.add(0);
        ls.add(1);
        ls.add(9);
        ls.add(9);
        ls.add(3);
        ls.add(4);
        AtomicInteger ii = new AtomicInteger();
        ls.stream().sorted().forEach(i ->{
            System.out.printf(" " + i);
        });
        System.out.println("-----");
        Object[] objects = ls.stream().sorted().toArray();
        int l = objects.length;
        if(l%2 == 0){
            System.out.println(Double.valueOf((Integer)objects[l/2]+(Integer)objects[l/2-1])/2);
        }else{
            System.out.println(objects[l/2]);
        }

        System.out.println("________");
        ls.stream().sorted().forEach(i -> {
            if(ii.getAndIncrement() == ls.size()/2){
                System.out.printf(String.valueOf(i));
            }
        });
        System.out.println("______");
        ls.stream().forEach(i -> {
            System.out.printf(i + " ");
                s.insert(i);
        });
        System.out.println("______");

        System.out.println(s.getMedium());
    }
}
